//最小生成树
//https://www.luogu.com.cn/problem/P3366
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//const int N = 5e3 + 10;
//int arr[N][N];  //邻接矩阵
//int n, m;
//bool check[N];	
//int dest[N];	//距离生成树的最小距离数组
//int INF = 0x3f3f3f3f;
//
//int prim()
//{
//	memset(dest, INF, sizeof dest);
//	dest[1] = 0;
//	int ret = 0;
//
//	//挑选 n 个节点加入到最小生成树中
//	for (int i = 1; i <= n; i++)
//	{
//		//找到最小的节点
//		int t = 0;
//		for (int j = 1; j <= n; j++)
//		{
//			if (!check[j] && dest[j] < dest[t]) t = j;
//		}
//
//		//判断是否能构成生成树
//		if (dest[t] == INF) return INF;
//
//		//加入生成树
//		ret += dest[t]; check[t] = true;
//		
//		//更新距离
//		for (int j = 1; j <= n; j++)
//		{
//			dest[j] = min(dest[j], arr[t][j]);
//		}
//	}
//
//	//返回结果
//	return ret;
//}

//int main()
//{
//	memset(arr, INF, sizeof arr);
//	cin >> n >> m;
//	for (int i = 0; i < m; i++)
//	{
//		int x, y, z; cin >> x >> y >> z;
//		//注意重边
//		arr[x][y] = arr[y][x] = min(arr[x][y], z);
//	}
//
//	int ret = prim();
//	if (ret == INF)
//	{
//		cout << "orz" << endl;
//		return 0;
//	}
//	cout << ret << endl;
//	return 0;
//}



//Kruskal 算法

const int N = 5e3 + 10;
int n, m;
int INF = 0x3f3f3f3f;

//并查集
int uf[N];

int find(int n)
{
	return uf[n] == n ? n : uf[n] = find(uf[n]);
}

//边的结构
struct side
{
	int a;	//起点
	int b;	//终点
	int len;//长度
}arr[N];

int Kruskal()
{
	//初始化并查集
	for (int i = 0; i < N; i++) uf[i] = i;
	sort(arr + 1, arr + 1 + m, [](const side& a,const side& b) {return a.len < b.len; });
	
	int count = 0;
	int ret = 0;
	//开始选边
	for (int i = 1; i <= m; i++)
	{
		int a = arr[i].a; int b = arr[i].b; int len = arr[i].len;

		int par1 = find(a); int par2 = find(b);
		if (par1 != par2)
		{
			count++; ret += len;
			//合并
			uf[par1] = par2;
		}
	}
	
	if (count != n - 1) return INF;
	return ret;
}

//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= m; i++)
//	{
//		int x, y, z; cin >> x >> y >> z;
//		arr[i].a = x; arr[i].b = y; arr[i].len = z;
//	}
//
//	int ret = Kruskal();
//	if (ret == INF)
//	{
//		cout << "orz" << endl;
//		return 0;
//	}
//	cout << ret << endl;
//	return 0;
//}